Spacial Logic

Remember the happy puppies?

happy_puppies.py

NOTES

• Copy happy_puppies.py from Friday's lecture to today's workspace

%%file happy_puppies.py
def is_happy(grid, row, column):
    if grid[row][column] != 'p':
        return False
    
    if row - 1 >= 0 and grid[row - 1][column] == 'p':
        return True
    if row + 1 < len(grid) and grid[row + 1][column] == 'p':
        return True
    if column - 1 >= 0 and grid[row][column - 1] == 'p':
        return True
    if column + 1 < len(grid[row]) and grid[row][column + 1] == 'p':
        return True
    
    if row - 1 >= 0 and column - 1 >= 0 and grid[row - 1][column - 1] == 'p':
        return True
    if row + 1 < len(grid) and column - 1 >= 0 and grid[row + 1][column - 1] == 'p':
        return True
    if row - 1 >= 0 and column + 1 < len(grid[row]) and grid[row - 1][column + 1] == 'p':
        return True
    if row + 1 < len(grid) and column + 1 < len(grid[row]) and grid[row + 1][column + 1] == 'p':
        return True
    
    return False


def find_happy(grid):
    happy = []
    for row in range(len(grid)):
        for column in range(len(grid[row])):
            if is_happy(grid, row, column):
                happy.append((row, column))
    return happy


grid = [
    [None, 'p', 'p'],
    ['p', None, None],
    [None, None, 'p']
]
find_happy(grid)

🧑🏼‍🎨 More Pups in a Grid

🐶 🐶 🐶 🐶 🐶
🐶 🐶 🐶 🐶 🐶
🐶 🐶 🐶 🐶 🐶
🐶 🐶 🐶 🐶 🐶
🐶 🐶 🐶 🐶 🐶

Breaking research! Puppies are actually happy if the are within barking distance of another puppy.

Let's update our code so that is_happy returns True is there is another puppy within two squares of the given puppy.

When we searched one square in each direction, we searched a 3x3 grid (minus the middle square) for a total of 8 positions.

To search two squares in each direction, we'll need to check 5 x 5 - 1 = 24 total positions!

😱

🎨 continue

print('A','B')
print('---')
for a in range(4):
    for b in range(4):
        if b > a:
            continue
        print(a,b)

NOTES

• Walk through this code
• Explain that continue skips to the next iteration of the inner-most loop
  • i.e. the "b" loop in our example

🎨 min, max

print(min(3, 7))

print(max(2, 8))

🖌 Windows

Given a list of items, write a function that returns all the items within radius steps of a given index.

NOTES

• Draw this out
  • draw 0 through 9
  • pick a position
  • draw the window around that position
    • when the window does not extend beyond a boundary, there are not problems
    • what are the two boundaries? 0, len(items)-1
  • we want the window to go from pos-size to pos+size+1, unless it runs into a boundary first
    • draw out examples of pos-size. When pos-size is negative, what value do we want to use instead?
    • draw out examples of pos+size+1. When pos+size+1 is > len(items)-1, what value do we want to use instead?
  • observe how the min and max clauses enforce the boundary constraints

index = 3, radius = 2
0 1 2 3 4 5 6 7 8 9
 [....^....]


index = 1, radius = 3
     0 1 2 3 4 5 6 7 8 9
[......^......]  # what we would get
    [..^......]  # what we want


index = 8, radius = 3
0 1 2 3 4 5 6 7 8 9
         [......^......]   # What we would get
         [......^..]       # What we want

def get_window(items, index, radius):
    """Return the items within `radius` steps from `index`. """
    # What is the lower bound of the range?
    # What is the upper bound of the range?
    # Iterate through that range and grab the items
    window = []
    return window

def get_window(items, index, radius):
    """Return the items within `radius` steps from `index`. """
    window = []
    min_bound = max(0, index - radius)
    max_bound = min(len(items), index + radius + 1)
    for position in range(min_bound, max_bound):
        window.append(items[position])
    return window

numbers = list(range(10))
print(get_window(numbers, 3, 1))

print(get_window(numbers, 4, 2))

print(get_window(numbers, 8, 2))

print(get_window(numbers, 1, 5))

Let's use these two new techniques to address our happy puppy problem.

more_happy_puppies.py

NOTES

• draw out the search problem in terms of a box around a position
  • show how we want to truncate the box if it extends beyond the edges of the grid
  • use the min/max technique to set the ranges for the row and column positions
• what do we want to do at the middle position? how do we know we are on the middle position?

def is_happy(grid, row, column, radius=1):
    if grid[row][column] != 'p':
        return False
    
    row_lower_bound = max(0, row - radius)
    row_upper_bound = min(len(grid), row + radius + 1)

    for r in range(row_lower_bound, row_upper_bound):
        
        col_lower_bound = max(0, column - radius)
        col_upper_bound = min(len(grid[row]), column + radius + 1)
    
        for c in range(col_lower_bound, col_upper_bound):
            
            if r == row and c == column: # middle position doesn't count
                continue
            if grid[r][c] == 'p':
                return True
    
    return False


def find_happy(grid, radius=1):
    happy = []
    for row in range(len(grid)):
        for column in range(len(grid[row])):
            if is_happy(grid, row, column, radius):
                happy.append((row, column))
    return happy


grid = [
    [None, 'p', 'p'],
    ['p', None, None],
    [None, None, 'p']
]
find_happy(grid, radius=2)

👩🏻‍🎨 Three In a Row

Write a function that returns True if there is any occurrence of three 'X' in a row (including diagonal).

three_in_a_row.py

test_three_in_a_row.py

NOTES

• Goal: help the students develop confidence in designing more complex logic through drawing out the problem

• DRAW IT OUT

  • draw an example grid
  • demonstrate the different directions we need to test
    • do we need to check both left AND right? No.
    • 4 directions needed. Name them. (e.g. "right", "down", "down-right", "down-left")
  • write out tests

• Write out has_three_in_a_row

  • for each position in the grid, if it has three in a row in any of our 4 directions, return True

• Now implement the 4 directions

  • Draw out the range for the row and the column
  • Highlight the boundary conditions: min and max values
  • Code an early return for violated boundary conditions
  • Code the loop over the variable dimension(s)
    • "right" and "down" have a constant in one dimension
    • use zip for variables in both dimensions
      • make sure the steps are synced correctly: have both ranges start at the row, column position and move out.
  • for each direction, add a test
    • include a positive and a negative test

def has_three_right(grid, row, column, value):
    if column + 3 > len(grid[row]):
        return False
    
    for c in range(column, column + 3):
        if grid[row][c] != value:
            return False
    
    return True


def has_three_down_right(grid, row, column, value):
    if column + 3 > len(grid[row]):
        return False
    
    if row + 3 > len(grid):
        return False
    
    for r, c in zip(range(row, row + 3), range(column, column + 3)):
        if grid[r][c] != value:
            return False

    return True


def has_three_down(grid, row, column, value):
    if row + 3 > len(grid):
        return False
    
    for r in range(row, row + 3):
        if grid[r][column] != value:
            return False

    return True


def has_three_down_left(grid, row, column, value):
    if column - 2 < 0:
        return False
    
    if row + 3 > len(grid):
        return False
    
    for r, c in zip(range(row, row + 3), range(column, column - 3, -1)):
        if grid[r][c] != value:
            return False

    return True


def has_three_in_a_row(grid, value='X'):
    for row in range(len(grid)):
        for column in range(len(grid[row])):
            if has_three_right(grid, row, column, value) \
            or has_three_down_right(grid, row, column, value) \
            or has_three_down(grid, row, column, value) \
            or has_three_down_left(grid, row, column, value):
                return True
    return False

from three_in_a_row import has_three_in_a_row, has_three_right



def test_has_three_in_a_row_right():
    grid = [
        [0, 0, 1],
        [0, 1, 0],
        [1, 1, 1]
    ]
    assert has_three_right(grid, 2, 0, 1)  # grid, row, column, value
    assert not has_three_right(grid, 2, 0, 0)  # grid, row, column, value
    assert not has_three_right(grid, 0, 0, 0)  # grid, row, column, value
    assert not has_three_right(grid, 1, 1, 1)  # make sure I don't run out of bounds
    

def test_has_three_in_a_row():
    grid = [
        [1, 0, 1],
        [0, 1, 0],
        [1, 1, 0]
    ]
    assert has_three_in_a_row(grid, value=1)
    
    
def test_not_has_three_in_a_row():
    grid = [
        [1, 0, 1],
        [0, 1, 0],
        [0, 1, 0]
    ]
    assert not has_three_in_a_row(grid, value=1)
    

def test_has_three_0_in_a_row():
    grid = [
        [1, 0, 1],
        [0, 0, 0],
        [0, 1, 0]
    ]
    assert not has_three_in_a_row(grid, value=0)
    
    

Key Ideas

• 2D logic
• continue
• min, max, and range to handle boundary conditions
• Searching a 2D subgrid